package main

import "fmt"

//节点类型
type ListNode struct {
	date int
	next *ListNode
}

type  LinkList struct {
	Head * ListNode
}

//创建单链表
func (l *LinkList) AddNode(date int){
	newnode :=&ListNode{date,nil}
	if l.Head == nil{
		l.Head =newnode
	}else {
		current := l.Head
		//找到最后一个节点
		for current.next != nil{
			current =current.next
		}
		current.next =newnode
	}

}

func (l *LinkList) reverse() {
	var prev *ListNode
	current := l.Head
	for current != nil {
		next := current.next
		current.next = prev
		prev = current
		current = next
	}
	l.Head = prev
}

//合并
func (l *LinkList) MergeLists(lst1 *LinkList, lst2 *LinkList) {
	if lst1 == nil {
		l.Head = lst2.Head
		return
	}
	if lst2 == nil {
		l.Head = lst1.Head
		return
	}

	if lst1.Head.date < lst2.Head.date {
		l.Head = lst1.Head
		lst1.Head = lst1.Head.next
	} else {
		l.Head = lst2.Head
		lst2.Head = lst2.Head.next
	}

	current := l.Head

	for lst1.Head != nil && lst2.Head != nil {
		if lst1.Head.date < lst2.Head.date {
			current.next = lst1.Head
			lst1.Head = lst1.Head.next
		} else {
			current.next = lst2.Head
			lst2.Head = lst2.Head.next
		}
		current = current.next
	}

	if lst1.Head != nil {
		current.next = lst1.Head
	}

	if lst2.Head != nil {
		current.next = lst2.Head
	}
}


//打印
func (l *LinkList) printList(){
	current :=l.Head
	for current != nil{
		fmt.Printf("%d ",current.date)
		current = current.next
	}
	fmt.Println()
}

func main()  {
	lst1 := LinkList{}
	lst1.AddNode(2)
	lst1.AddNode(5)
	lst1.AddNode(8)
	lst1.AddNode(10)

	lst2 := LinkList{}
	lst2.AddNode(3)
	lst2.AddNode(4)
	lst2.AddNode(6)
	lst2.AddNode(9)


	lst := LinkList{}
	lst.MergeLists(&lst1,&lst2)
	lst.printList()

}